Orthogonal transforms and transform properties are extraordinarily useful in solving new technological problems. Such transforms permit analysis of a signal given some knowledge of its constituent parts. For example, the Fourier transform has long been a powerful and principle analysis tool in diverse fields, such as linear systems, probabililty theory, boundary-valued problems, communications theory, signal processing, etc. The discrete Fourier transform (DFT) is the counterpart of the Fourier transform in the screte time domain. In general, the DFT may be defined as follows: ##EQU1## and the inverse DFT (IDFT) is expressed as: ##EQU2## where W.sub.N.sup.k =e.sup.-j2.pi.k/N. In equations (1) and (2), x(n) is the sample value in the time domain, and X(k) is the sample value in the frequency domain.
Direct computation of the DFT and the IDFT requires N.sup.2 complex multiplications and N(N-1) complex additions. Such data processing overhead is quite onerous. One helpful and important tool in modem digital signal processing applications is therefore the fast Fourier transform (FFT). The FFT is an efficient algorithm for computing the DFT by mapping an N-point complex sequence to its corresponding N-point complex frequency spectrum.
Although most FFT algorithms are designed to compute the DFT of a complex sequence, in many applications, the sequence to be transformed is real valued. Nevertheless, even in these real valued applications, the FFT algorithm performs multiple complex multiplications and additions. Even with the increased efficiency and speed provided using the FFT algorithm, there is an ongoing need to reduce the number of computations, and in particular, the number of complex multiplications that must be performed in order to more efficiently compute the DFT and the IDFT.
The present invention achieves a significant reduction in the number of complex computations that must be performed in computing the DFT and IDFT. In particular, the DFT and IDFT operations are computed using the same computing device with the computation operations being substantially identical for both operations with the exception that for the IDFT operation, the data are complex conjugated before and after processing. Using the same computing device/operations, both DFT and IDFT computations are optimized for maximum efficiency. Indeed, efficiency improvement is on the order of 50 percent compared with more traditional, brute force FFT/IFFT computations.
A data processing device employing the present invention includes first and second data processing paths. A transform process (in particular a DFT processor) is selectively connected to the first and second data processing paths, and selectively performs a DFT operation on an N-point complex sequence in the time domain present on the first data processing path and an IDFT on an N-point complex sequence in the frequency domain present on the second data processing path using the same N-point fast Fourier transform. For purposes of this invention, N is a positive integer, and the term point is the number of symbols in a sequence. Each such sequence symbol is considered a complex number whether or not the symbol includes both real and imaginary parts. In the frequency domain, a symbol may be viewed as a spectral component.
The first data processing path corresponds to the DFT operation, and the second data processing path corresponds to the IDFT operation. In a particularly advantageous application of the invention, a 2N-point, real sequence in the time domain is translated into the frequency domain via the first data processing path. The 2N-point real sequence is compressed into an N-point complex sequence before routing to the transform processor. The N-point complex data are transformed using an N-point DFT operation executed by the transform processor, and the transform processor output is then translated into an N-point spectral sequence in the frequency domain.
Along the second data processing path, an N-point, complex spectral sequence, instead of being extended to a 2N-point Hermite symmetric sequence as required to obtain a real sequence in the time domain, is processed to generate an N-point spectral input sequence, which when processed by the transform processor, results in an N-point sequence in the time domain. The N-point output sequence is complex conjugated, and then converted from an N-point complex sequence into a 2N-point real sequence.
In one advantagous application of the present invention to data communications, the first data processing path corresponds to a portion of a receiver, and the second data processing path corresponds to a portion of a transmitter. The receiver and transmitter may function for example as a modem. One preferred modem type is a discrete, multi-tone (DMT) modern. The transmit data processing path modulates a symbol sequence onto multiple carriers, and the receive data processing demodulates the multiple carriers and reconstructs the transmitted symbol sequence.
Because both transmitter and receiver data processing paths use the same DFT processor to perform frequency-to-time and time-to-frequency transformations, e.g., DMT modulation and demodulation, a more economic transceiver may be achieved in terms of efficiency, size, expense, complexity, and power dissipation. In the DMT modem example, the same, N-point Fourier transform performs IDFT modulation of a symbol sequence having in effect twice that number of points in the sequence as well as DFT demodulation of received signals also having 2N-points. It is in this fashion that the present invention is able to reduce the computational complexity of the transformation operations by approximately 50 percent, i.e., from 2Nlog.sub.2 2N complex multiplications to Nlog.sub.2 2N complex multiplications.
Thus while the primary object of the present invention is to provide a particulary efficient method and apparatus for DFT/IDFT computations, these and other objects and advances of the present invention will become apparent to those skilled in the art as described below in further detail, and in conjunction with the figures and the appended claims.